package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/n-ary-tree-postorder-traversal/">N 叉树的后序遍历(N-ary Tree Postorder Traversal)</a>
 * <p>给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。</p>
 * <p>n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,null,3,2,4,null,5,6]
 *                    1
 *                 /  |  \
 *                3   2   4
 *               / \
 *              5   6
 *      输出：[5,6,3,2,4,1]
 *
 * 示例 2：
 *      输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 *      输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>节点总数在范围 [0, 10^4]内</li>
 *     <li>0 <= Node.val <= 10^4</li>
 *     <li>n 叉树的高度小于或等于 1000</li>
 * </ul>
 * </p>
 * <b>进阶：递归法很简单，你可以使用迭代法完成此题吗?</b>
 *
 * @author c2b
 * @see LC0429NaryTreeLevelOrderTraversal_M N 叉树的层序遍历(N-ary Tree Level Order Traversal)
 * @see LC0589NaryTreePreorderTraversal_S  N 叉树的前序遍历(N-ary Tree Preorder Traversal)
 * @see LC0590NaryTreePostorderTraversal_S N 叉树的后序遍历(N-ary Tree Postorder Traversal)
 * @since 2025/2/8 13:54
 */
public class LC0590NaryTreePostorderTraversal_S {


    static class Solution {
        public List<Integer> postorder(Node root) {
            //return postorderByIterator(root);
            return postorderByRecursion(root);
        }

        private List<Integer> postorderByIterator(Node root) {
            List<Integer> resList = new ArrayList<>();
            if (root == null) {
                return resList;
            }
            Deque<Node> stack = new LinkedList<>();
            stack.addFirst(root);
            while (!stack.isEmpty()) {
                Node currNode = stack.removeFirst();
                resList.add(0, currNode.val);
                List<Node> children = currNode.children;
                if (children != null) {
                    for (Node child : children) {
                        stack.addFirst(child);
                    }
                }
            }
            return resList;
        }

        private List<Integer> postorderByRecursion(Node root) {
            List<Integer> resList = new ArrayList<>();
            postorderByRecursion(root, resList);
            return resList;
        }

        private void postorderByRecursion(Node root, List<Integer> resList) {
            if (root == null) {
                return;
            }
            List<Node> children = root.children;
            if (children != null) {
                for (Node child : children) {
                    postorderByRecursion(child, resList);
                }
            }
            resList.add(root.val);
        }

        private static class Node {
            public int val;
            public List<Node> children;

            public Node() {
            }

            public Node(int _val) {
                val = _val;
            }

            public Node(int _val, List<Node> _children) {
                val = _val;
                children = _children;
            }
        }
    }
}
